Math Games

Rulers, Arrays, and Gracefulness

Ed Pegg Jr., November 15, 2004

In 1952, seemed to solve distortion problems in consecutive radio bands. Wallace C. Babcock found that the optimal way to set up radio signals involved placing them at fixed points so that all distances between signals were distinct. From that basis, he optimized signals within a minimum bandwidth - completely eliminating third order distortion while reducing fifth order distortion. His optimal array placed channels within the frequency spectrum at positions {0, 1, 4, 9, 15, 22, 32, 34}. No two distances are repeated. From 1 to 34, all distances except {16, 20, 24, 26, 27, 29}appear.

Solomon Golomb became interested in this intermodulation-avoidance array, and changed the problem to a ruler with minimal markings. He noted was perfect -- each distance from 1 to 6 appeared exactly once -- and wondered if more perfect rulers were possible. Unfortunately, he proved that this was the largest perfect ruler. Golomb rulers were named as a result of his investigations.

Consider the following curious triangle (Figure 1). Note that CH=1, BF=2, AD=3, BE=4, ..., BD=16, AH=17, AC=18, AB=19. There are a total of 18 different possible distances along the edges, with none repeated. All distances from 1 to 19 can be measured, except 14.

Figure 1. DΔS M(3,3) gives 18 distinct distances in a scope of 19. (See J B Shearer's page.)

The triangle can be represented as {{0,3,15,19}, {0,6,11,13}, {0,8,17,18}}, and gives an optimal difference triangle set, or DΔS. The maximal distance, or scope, must be as small as possible. For M(3,3), the scope is 19. A triangle with 6 marks on each side, M(3,7) = {{0,12,15,31,55,87,88,93}, {0,7,30,41,51,77,90,99}, {0,2,29,37,54,82,96,100}}, measures 84 distinct distances with scope 100. M(3,8) is currently unknown.

Triangles seem interesting -- how about a 2 sided object? The largest known DΔS of this type is M(2,9), shown below.

Figure 2. DΔS M(2,9) gives 90 distinct distance in a scope of 121. (See J B Shearer's page.)

The above use marks on two or three lines. If the marks are placed on just a single line, and no shorter ruler is possible, it's a Golomb ruler. All Golomb rulers up to 8 marks were originally discovered by Wallace C. Babcock. The rest have been discovered through both combinatorial analysis and impressive computer power. The following table contains examples of all known rulers up to 24 marks. The years given are the verification dates, and not necessarily the year a particular ruler was originally discovered.

Rulers with 20 to 22 marks were found with an intense computer search by Mark Garry and David Vanderschel. For rulers with 23 and 24 marks, work got started at distributed.net. They sent out a press release on 1 November 2004:

A picture of OGR-24 can be seen at hewgill.com. I don't think they are serious about that last comment -- can you imagine how big the party would be? Let me turn that question around: can you figure out how big a Golomb ruler will be? For n marks, we know that G(n) gives the sequence 0, 1, 3, 6, 11, 17, 25, 34, 44, 55, 72, 85, 106, 127, 151, 177, 199, 216, 246, 283, 333, 356, 372, 425. (A003022). Above 4 marks, we know that (n-1)(n-2)<G(n)<n². Can a better bound be found? To answer that question, one must delve farther back into history.

As earlier mentioned, they are named Golomb rulers, but were actually discovered by Babcock. Before that, in 1932, Simon Sidon looked at subsets of the natural numbers up to n such that no two pairs of numbers had a common sum. (In a Golomb ruler, no two pairs of numbers have a common difference.) Paul Erdos called them Sidon sets, and published papers about them in 1934. Apostolos Dimitromanolakis proved the equivalence of the two in 2002. It was very easy: Sidon <=> NOT(a_r+a_s= a_m+a_n) <=> NOT(a_r-a_n = a_m-a_s) <=> Golomb. Dimitromanolakis used this connection to find the lower bound G(n)>n^2-2n*sqrt(n)+sqrt(n)-2.

So, we have some sequence of marks, {0, 1, 4, 9, 15, 22, 32, 34}, and we demand that the differences on every level be different: {{1, 3, 5, 6, 7, 10, 2}, {4, 8, 11, 13, 17, 12}, {9, 14, 18, 23, 19}, {15, 21, 28, 25}, {22, 31, 30}, {32, 33}, {34}}. What if the restriction is lessened, so that the distances must be distinct within each level? These are called Costas arrays. They are used in the fields of radar, sonar, and communications -- and it turns out the best introduction about them was written by Solomon W. Golomb and Herbert Taylor.

Currently, the only way to determine all Costas arrays of a given order is through exhaustive search, although many may be produced through algebraic constructions. As a simple example, consider the prime number 19, and compute the values of (2^k) mod 19, k = 0:17. The result is the following sequence: 1, 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10.

This sequence is not only a permutation of the integers from 1 to 18, but also has the property that each row of its triangular difference table contains unique differences. This property is similar to Golomb rulers, except the differences are allowed to be negative or positive, and uniqueness is only enforced within a given row.

For some time, only the Costas arrays up to order 23 were known, giving sequence A008404. In April 2004, it was announced at the IEEE Radar Conference that 200 distinct Costas arrays exist for n=24, and 88 exist for n=25.

Sparse rulers are more practical as actual rulers. , for example, will measure all distances up to 29. It has an excess of seven extra distances {1, 2, 3, 3, 6, 13, 27}. One obvious problem is to minimize excess for n marks. Sparse rulers don't seem to be well studied -- the best source I found for them was David Fowler's article at the Mathematica Information Center, of all places.

A similar problem involves labeling the vertices of graphs such that the n edges represent the difference between the vertices. If the edges contain the values 1 to n, it is considered to be a graceful graph. A famous unsolved problem: Characterize the graceful graphs (S. Golomb, 1972). As an example, the Petersen graph is graceful. Joseph Gallian maintains a survey of what is known on graceful graphs.

Figure 4. The graceful Petersen graph.

Thousands of computers are working to extend the results mentioned above. Curiously, these massive computer searches have been verifying what is already known: the OGR-24 result was verified 1 November 2004, but it was originally discovered in 1967 (!) by John P. Robinson and Arthur J. Bernstein. The rulers to beat are maintained by James Shearer, and consist mainly of constructions via affine and projective planes. The last 8 proven rulers have used thousands of years of computer time to verify the results of a few clever combinatorialists from over 30 years ago. The OGR-25 project will try to top the 1984 result of Atkinson and Hassenklover. In this battle between two combinatorialists and one of the world's largest distributed computer systems, I'll side with the two math guys.

W. C. Babcock, "Intermodulation Interference in Radio Systems", Bell System Technical Journal, 1953, p. 63-73.

James Beard, Jon Russo, Keith Erickson, Michael Monteleone, and Mike Wright, "Combinatoric Collaboration on Costas Arrays and Radar Applications," IEEE Radar Conference, Philadelphia, PA, April 2004. http://www.radar04.org/program/index.cgi?paper=144.

Justin Colannino, " Circular and Modular Golomb Rulers," http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/JustinColannino/.

distributed.net, "Project OGR," http://www.distributed.net/ogr/.

Apostolos Dimitromanolakis, "Analysis Of The Golomb Ruler And The Sidon Set Problems And Determination Of Large Near-Optimal Golomb Rulers," http://citeseer.ist.psu.edu/dimitromanolakis02analysis.html.

Apostolos Dollas, William T. Rankin, David McCracken, "New Algorithms for Golomb Ruler Derivation and Proof of the 19 Mark Ruler," http://www.ee.duke.edu/~wrankin/golomb/golomb.html.

Paul Erdos and P. Turan. "On a problem of Sidon in additive number theory, and on some related problems," J. London Math. Soc, 16:212--215, 1941.

Frans Faase, "Sparse rulers," http://home.planet.nl/~faase009/Ha_sparse_rulers.html.

David Fowler, "Genetically Seeking Sparse Rulers," Mathematica in Education and Research, V9:2, 2000, p 33-40. http://library.wolfram.com/infocenter/Articles/3820/.

Joseph A. Gallian, "Graph Labeling," http://www.combinatorics.org/Surveys/.

Mark Garry, David Vanderschel, "In Search Of The Optimal 20, 21 & 22 Mark Golomb Rulers," http://members.aol.com/golomb20/.

Martin Gardner, "Mathematical Games", Scientific American, March 1972, p. 108-112.

Solomon W. Golomb, Herbert Taylor, "Construction and Properties of Costas Arrays", Proceedings of the IEEE, Vol. 72, No. 9, September 1984.

Solomon W. Golomb, "How to Number a Graph." In Graph Theory and Computing (Ed. R. C. Read). New York: Academic Press, pp. 23-37, 1972.

Bill Rankin, "Golomb Ruler Calculations," http://www.ee.duke.edu/~wrankin/golomb/golomb.html.

Walter Schneider, "Golomb Rulers," http://www.wschnei.de/number-theory/golomb-rulers.html.

James B. Shearer, "Difference Triangle Sets," http://www.research.ibm.com/people/s/shearer/dts.html.

James B. Shearer, "Smallest Known Golomb Rulers," http://www.research.ibm.com/people/s/shearer/grtab.html.

N. J. A. Sloane, Sequences A000217, A003022, A036501, and A039953 in "The On-Line Encyclopedia of Integer Sequences." http://www.research.att.com/~njas/sequences/.

Eric W. Weisstein. "B2-Sequence, Graceful Graph, Golomb Ruler" From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/.

Comments are welcome. Please send comments to Ed Pegg Jr. at ed@mathpuzzle.com.

Ed Pegg Jr. is the webmaster for mathpuzzle.com. He works at Wolfram Research, Inc. as an associate editor of MathWorld, and as administrator of the Mathematica Information Center.